1. Field of the Invention
This invention relates to improvements in methods and apparatus for allocating and reclaiming memory in symbolic processing type systems, and more particularly to methods and apparatus relating to incremental, multi-area, generational, copying garbage collection in a virtual address space which can be associated with an artificial intelligence engine, or the like.
2. Description of Related Art Including Information Disclosed Under .sctn..sctn.1.97-1.99
The method and apparatus of the invention has particular application to systems which use symbolic processing languages and techniques. In the past, memory spaces associated in the operation of such computer systems were relatively small, and the reclamation of memory space, referred to as "garbage collection" was not a significant problem. Generally, when the memory was in need of garbage collection, the CPU processes were stopped, or "paused", and a garbage collection process was performed. However, as larger and larger memories are possible of implementation, and recent interest in very large memory operations, such as artificial intelligence applications, have been receiving more and more attention, the problems associated with garbage collection have become of greater importance.
In approaches to this problem, pausing garbage collectors have been advanced, usually with the accompanying assumption that there will be times when pauses in the CPU processes could be tolerated. Again, however, when larger memories, such as memories of 2.sup.26 or 2.sup.32 words have been considered, collection of the entire memory takes sometimes minutes, or even hours to complete. (It has sometimes been assumed that the system operator may "go home" at night, and during that period of inactivity, the garbage collection process could be run on larger systems.)
In efforts to minimize the delay effects of such garbage collection on the system operation, it has been proposed to create "generations" of work, with progressively older generations being defined, then pausing the CPU operation to collect certain generations, so that the entire memory is not collected at one time. This has resulted in garbage collection "pauses" of lesser time, but noticeable pauses still result.
In efforts to achieve "real-time" garbage collection, it has been proposed to divide the memory into two semispaces, often referred to as "oldspace" and "newspace", and to copy all the non-garbage objects from the oldspace to the newspace. A forwarding address is left at the old location, in oldspace, of a copied object. Whenever a pointer is followed which points to an object containing a forwarding address, the pointer is updated to point to the copied object. The processor is shared among the CPU processes and the garbage collection process. Collection is complete when all reachable objects have been copied to newspace. Again, however, the collection process on the entire memory is inefficient, and often requires unnecessarily moving memory contents.
It has also been proposed to define a number of different areas in the memory, and to collect only one area at a time to achieve more realistic "real-time" collection. These attempts also have significant disadvantages.